package gold.digger;

import gold.vo.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC142 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
    * @param 此题目参考了别人代码
    * 这是因为问题情况较为复杂
    * 未来需要再次复习此道题目
    * @return:
    */
    public class Solution {
        private ListNode getIntersect(ListNode head) {
            ListNode tortoise = head;
            ListNode hare = head;

            // A fast pointer will either loop around a cycle and meet the slow
            // pointer or reach the `null` at the end of a non-cyclic list.
            while (hare != null && hare.next != null) {
                tortoise = tortoise.next;
                hare = hare.next.next;
                if (tortoise == hare) {
                    return tortoise;
                }
            }

            return null;
        }

        public ListNode detectCycle(ListNode head) {
            if (head == null) {
                return null;
            }

            // If there is a cycle, the fast/slow pointers will intersect at some
            // node. Otherwise, there is no cycle, so we cannot find an e***ance to
            // a cycle.
            ListNode intersect = getIntersect(head);
            if (intersect == null) {
                return null;
            }

            // To find the e***ance to the cycle, we have two pointers traverse at
            // the same speed -- one from the front of the list, and the other from
            // the point of intersection.
            ListNode ptr1 = head;
            ListNode ptr2 = intersect;
            while (ptr1 != ptr2) {
                ptr1 = ptr1.next;
                ptr2 = ptr2.next;
            }

            return ptr1;
        }
    }


    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC142 an = new LC142();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
